#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

 struct ListNode {
      int val;
      struct ListNode *next;
  };
//对链表进行插入排序
struct ListNode* insertionSortList(struct ListNode* head) 
{
    if(head==NULL||head->next==NULL)
        return head;
    struct ListNode* sorthead=head;
    struct ListNode* cur=head->next;
    sorthead->next=NULL;
    while(cur)
    {
        struct ListNode* next=cur->next;
        //头插
        if(cur->val<=sorthead->val)
        {
            cur->next=sorthead;
            sorthead=cur;
        }
        else
        {
            struct ListNode* sortcur=sorthead;
            struct ListNode* sortnext=sortcur->next;
            //中间插入
            while(sortnext)
            {
                if(cur->val<=sortnext->val)
                {
                    sortcur->next=cur;
                    cur->next=sortnext;
                    break;
                }
                else
                {
                    sortcur=sortnext;
                    sortnext=sortnext->next;
                }
            }
            //尾插
            if(sortnext==NULL)
            {
                sortcur->next=cur;
                cur->next=NULL;
            }


        }
        cur=next;
    } 
    return sorthead;   
}